1. Field of the Invention
The present invention generally relates to semiconductor memory devices, and particularly relates to a content addressable memory.
2. Description of the Related Art
A Content addressable memory (CAM) is a memory device that receives data as an input, and outputs an address. A CAM detects data that matches input data within a memory area, and outputs an address at which the matched data is stored. The input data is referred to as an entry key, and the stored data are called entry data.
FIG. 1 is an example of a cell used in a CAM.
A CAM cell 10 of FIG. 1 includes NMOS transistors 11 through 16 and inverters 17 and 18. The inverters 17 and 18 together form a latch that stores therein one bit data. When the CAM cell 10 stores xe2x80x9c1xe2x80x9d therein, the data is latched such that a node N1 and a node N2 are xe2x80x9c1xe2x80x9d and xe2x80x9c0xe2x80x9d, respectively. When the CAM cell 10 stores xe2x80x9c0xe2x80x9d therein, the data is latched such that the node N1 and the node N2 are xe2x80x9c0xe2x80x9d and xe2x80x9c1xe2x80x9d, respectively. The storing of data is carried out by supplying the data to bit lines BL and /BL and activating a word line WL.
An entry key is provided through a search bus SB and /SB. When the entry key is xe2x80x9c1xe2x80x9d, the search bus lines SB and /SB are xe2x80x9c1xe2x80x9d and xe2x80x9c0xe2x80x9d, respectively. When the entry key is xe2x80x9c0xe2x80x9d, the search bus lines SB and /SB are xe2x80x9c0xe2x80x9d, and xe2x80x9c1xe2x80x9d, respectively.
In an initial state, a match line ML is precharged to HIGH. An entry key is then supplied to the CAM cell 10 through the search bus SB and /SB. If a 0/1 data combination of the search bus SB and /SB matches a 0/1 data combination of the entry data stored in the CAM cell 10, the match line ML stays HIGH. If they do not match, the NMOS transistors 11 and 13 simultaneously become conductive, or the NMOS transistors 12 and 14 simultaneously become conductive, so that the match line ML is coupled to the ground to become LOW.
A plurality of CAM cells identical to the CAM cell 10 as described above are provided to store entry data comprised of a plurality of bits, and are connected to the same match line ML in parallel. This provision makes it possible to check a match/mismatch status of an entry key comprised of a plurality of bits.
FIG. 2 is an illustrative drawing showing a configuration in which a plurality of CAM cells 10 are connected to a common match line.
As shown in FIG. 2, a plurality of CAM cells 10 are connected to the same match line ML. If any one of the CAM cells 10 does not match an entry key, i.e., if there is a difference of even a single bit between the entry data and the entry key, the match line ML that has been precharged to HIGH in the initial state is coupled to the ground to be pulled down. If the entry data and the entry key match, the match line ML stays HIGH.
The match line ML is connected to a match line sense amplifier (MLSA) 20 and a match line precharge circuit 21. The match line sense amplifier 20 is mainly comprised of a differential amplifier, and detects the signal level of the match line ML by comparing the potential of the match line ML with a reference potential. The match line precharge circuit 21 precharges the match line ML to a HIGH potential after the data detection by the match line sense amplifier 20. This completes preparation for a next data search.
FIG. 3 is a drawing showing voltage changes of the match line ML at the time of a data search.
As shown in FIG. 3, when a data search starts by comparing entry data with an entry key, the potential of the match line ML is brought down to the ground potential in the case of a data mismatch. In the case of a data match, however, the potential of the match line ML exhibits almost no change from the precharge potential. After the data detection by the match line sense amplifier 20, the match line precharge circuit 21 starts a precharge operation. Through this operation, the potential of the match line ML is set to the precharge potential.
In content addressable memory devices, a plurality of match lines are provided, and comparison of an entry key with entry data is made separately for each match line. That is, the entry key supplied through the search bus is compared on a bit-by-bit basis with entry data represented by a plurality of CAM cells sharing the same match line, and such comparison is made with respect to each match line. The potential of each match line changes according to a match or mismatch status of each data.
If there is more than one match line showing a data mismatch, therefore, there is more than one match line that is brought down to the ground potential. Precharging all the match lines that have been brought down to the ground potential requires a large electric power, resulting in large power consumption in the content addressable memory devices.
Accordingly, there is a need for a content addressable memory device in which power consumption is reduced with respect to precharging operations.
It is a general object of the present invention to provide a content addressable memory device that substantially obviates one or more of the problems caused by the limitations and disadvantages of the related art.
Features and advantages of the present invention will be set forth in the description which follows, and in part will become apparent from the description and the accompanying drawings, or may be learned by practice of the invention according to the teachings provided in the description. Objects as well as other features and advantages of the present invention will be realized and attained by a content addressable memory device particularly pointed out in the specification in such full, clear, concise, and exact terms as to enable a person having ordinary skill in the art to practice the invention.
To achieve these and other advantages and in accordance with the purpose of the invention, as embodied and broadly described herein, a content addressable memory device according to the present invention includes a first match line which is a first one of two portions into which a whole match line corresponding to a single item of entry data is divided, and changes from a first potential to a second potential when corresponding entry data does not match an entry key, a second match line which is a second one of the two portions into which the whole match line corresponding to the single item of entry data is divided, and changes from a second potential to a first potential when corresponding entry data does not match an entry key, a first precharge circuit which precharges the first match line to the first potential, a second precharge circuit which precharges the second match line to the second potential, and a short-circuiting circuit which short-circuits the first match line and the second match line with each other prior to precharging by the first and second precharge circuits if both of the first and second match lines indicate a mismatch.
In the content addressable memory device as described above, the first match line is precharged from the midlevel potential following the short-circuiting to the first potential, and the second match line is precharged from the midlevel potential following the short-circuiting to the second potential. When the first and second potentials are HIGH and LOW potentials, respectively, precharging of the second match line is performed by simply discharging electric charge stored in the wire capacitance of the match line, and does not need any power supplied from the exterior of the content addressable memory device. Accordingly, electric power that is required for the precharging operation is equal to the electric power that precharges the first match line from the midlevel potential to the HIGH potential. This is a quarter of the power required in a conventional configuration in which a match line twice as long is precharged from the ground potential to the HIGH potential.
In reality, since some of the match lines are precharged to the LOW potential in the present invention, additional power is required in the case of a data mismatch in order to bring up a match line from the ground potential to a HIGH potential such as the power supply potential by supplying power from a CAM cell. Since precharging to LOW is performed with respect to the second match line, the second match line needs to be pulled up from LOW to HIGH at the time of a mismatch determination. This requires half as much the electric power as required in the conventional precharge operation that precharges a match line twice as long from the LOW potential to the HIGH potential.
Accordingly, the configuration of the present invention completes one cycle of operations from a match/mismatch check to a precharge operation by spending xc2xe of the electric power that is required for the conventional precharge operation where xc2xe of the electric power is a sum of xc2xc of the electric power for a precharge operation and xc2xd of the electric power for a match/mismatch check. Even if no short-circuiting is performed because only one of the paired match lines exhibits a mismatch, pulling up one of the match lines from LOW to HIGH at the time of a precharge operation or a mismatch determination involves only half the capacitance load of a conventional match line, thereby requiring only xc2xd of the conventionally required electric power.
According to another aspect of the present invention, a method of precharging a content addressable memory includes the steps of precharging a first match line to a first potential, the first match line corresponding to a first portion of entry data, precharging a second match line to a second potential, the second match line corresponding to a second portion of the entry data, changing the first match line from the first potential to the second potential in response to a mismatch between a first portion of an entry key and the first portion of the entry data, changing the second match line from the second potential to the first potential in response to a mismatch between a second portion of the entry key and the second portion of the entry data, short-circuiting the first match line and the second match line with each other if the first match line is at the second potential and the second match line is at the first potential, precharging to the first potential the first match line that is at a midlevel potential between the first potential and the second potential after the short-circuiting, and precharging to the second potential the second match line that is at the midlevel potential after the short-circuiting.
Other objects and further features of the present invention will be apparent from the following detailed description when read in conjunction with the accompanying drawings.